//
//  RBT.hpp
//  RBT
//
//  Created by chenyh on 2021/2/18.
//

#ifndef RBT_hpp
#define RBT_hpp

#include <iostream>
/**
 红黑树是一种特殊的二叉查找树，它能够保证在最坏情况下基本操作的时间复杂度为 O(log2n)。这种数据结构避免了普通二叉树基本操作与树高度成正比的劣势，是一种常用 的重要数据结构。本节将介绍红黑树的定义和基本操作，并给出一些应用实例供参考。
 */
/**
 红黑树是一种二叉查找树，但是在每个结点的存储结构中多了一个颜色域 color 来对
 结点进行着色。结点要么是红色要么是黑色，所以红黑树的结点的结构如图 2-17 所示。
 图 2-17 红黑树结点结构
 一棵满足红黑性质的二叉查找树就是红黑树，红黑树性质的表述如下:
 性质1 每个结点或者是红的，或者是黑的。
 性质2 根结点一定是黑的。
 性质3 每个叶结点是黑的。
 性质4 如果一个结点是红的，则它的两个孩子结点都是黑的。
 性质5 对每个结点，对该结点到其子孙结点的所有路径上包含相同数目的黑结点。
 在红黑树中，我们将结点分为内结点和外结点两类。内结点是指具有关键字的结点，
 而我们把没有孩子结点或父结点的结点的相应为 NULL 的指针，视为指向二叉查找树的外 结点的指针。所以这里的外结点也就是我们在前面所介绍的几种树结构的 NULL 指针，我 们也称它为红黑树的叶子结点。这里要特别注意，红黑树中的叶子结点的概念与普通树的 叶子结点概念不同，这里的叶子结点没有关键字。
 
 */

/**
 红黑树的结构如图 2-18 所示。指针为 NULL 的结点就是叶子结点也就是红黑树的外 结点。从它的结构我们也可以发现，红黑树的叶子结点都是没有关键字的 NULL 指针空结 点，如果按照图 2-18 所示构造方式，无疑会浪费很多的存储空间，所以我们可以设想用一 个结点来表示这些同样的叶子结点。在这里我们设置边界哨兵结点 nil 来代表所有的叶 子结点。nil 结点是一个与树内结点有相同结构的结点，它的 color 值为 black，而它的其 他域值可以为允许的任意值，也可以为 NULL。所以我们得到红黑树的新结构如图 2-19 所示。
 */
/**
 性质 5 说明红黑树的任意一个结点 x 到大它的叶结点(nil)的任意一条路径上，黑结 点的个数相等。所以对于一个红黑树而言，这个黑结点的个数是一个确定的数，我们称之 为结点 x 的黑高度，一棵红黑树的黑高度是指该树的根结点的黑高度。
 根据二叉查找树的基本性质和红黑树的特性，我们得出一个如下的定理:
 引理 一棵有 n 个内结点的红黑树的高度之多为 2lg(n+1)。 上面的引理给了我们一个很好的提示，红黑树的查询、获取最大最小值等基本操作的
 时间复杂度为 O(lgn)，因为这些二叉查找树的基本操作的操作时间与树的高度有关。2.5.2 节会给出红黑树的基本操作的分析。
 */
//2.5.2 红黑树的基本操作
//红黑树的基本操作包括旋转、插入结点和删除结点。本节定义的红黑树如下:

/***红黑树结点定义***/
template<typename DataType> class RBT;
template<typename DataType> class RBTNode
{
    friend class RBT<DataType>;
private:
    RBTNode<DataType> *lChild,*rChild,*parent;//声明左孩子/右孩子和父结点指针
    DataType data;  //数据域
    int color;      //颜色域，0表示黑，1表示红
public:
    RBTNode()
    {
        lChild=rChild=parent=NULL;
        color = 0;  //颜色为黑色
        data  = NULL;
    }
    RBTNode(DataType d,int color) //构造内结点
    {
        data = d;
        lChild=rChild=parent=NULL;
        color = color;  //颜色为黑色
    }
    /**析构函数*/
    ~RBTNode()
    {
        lChild=rChild=parent=NULL;
        delete this;
    }
};
/***红黑树定义***/
template<typename DataType> class RBT
{
private:
    RBTNode<DataType> *root;    //根结点指针
    RBTNode<DataType> *nil;     //哨兵叶子结点
    int count;                  //结点数目
public:
    RBT()
    {
        root = NULL;
        nil = new RBTNode<DataType>();
        count = 0;
    }
    RBT(DataType data)
    {
        root = new RBTNode<DataType>(data,0);
        nil = new RBTNode<DataType>();
        count = 1;
    }
    /**左旋转*/
    void leftRotated(RBTNode<DataType> *node);
    /**插入结点*/
    void insert(RBTNode<DataType> *node);
};

/**
 红黑树的旋转操作是一种保持红黑树性质的操作，是红黑树插入和删除结点操作的基 础。旋转操作包括左旋和右旋，这两个操作是对称操作，这里以左旋为例进行讲解。
 对红黑树的结点 x 进行左旋时，我们假设 x 的右孩子不是 nil 结点，设右孩子为 y 结 点，旋转以 x 与 y 的连轴线为支撑逆时针旋转，旋转后使得 y 成为 x 所在子树的新的根结 点，x 成为 y 的左孩子，y 以前的左子树成为 x 的右子树。
 */


/**左旋转*/
template <typename DataType>
void RBT<DataType>::leftRotated(RBTNode<DataType> *node) {
    
    if (node->rChild != nil) { //判断node结点的右孩子是否为nil
        RBTNode<DataType> *y = node->rChild; //设置结点y为node的右孩子
        node->rChild = y->lChild;   //左旋之后y结点的左孩子成为node的右孩子
        if (y->lChild != nil) {
            y->lChild->parent = node;//如果y的左孩子不为空，则将其父结点设为node
        }
        y->parent = node->parent;   //将y的父结点设为node父结点
        if (node->parent == nil) {
            root = y;
        }
        else if (node->parent->lChild == node) //判断node是父结点的左孩子还是右孩子更改为y
        {
            node->parent->lChild = y;
        }else {
            node->parent->rChild = y;
        }
        y->lChild = node;       //y结点的左孩子更改为node
        node->parent = y;       //node的父结点更改为y
    }
}

/**
 2.插入结点
 在对红黑树插入新结点之后，很可能会造成红黑树性质的破坏。为了降低这种破坏程 度，我们将每一个新插入的结点的 color 设置为 red，然后先按照一般二叉查找树的插入操 作进行。这样必然会将新结点插入到某一个叶子结点的后面。这时我们就要分析一下，红 黑树的性质有没有被破坏，破坏了哪几条性质。很显然，红黑树的性质 1、3 是不会被破坏 的，又由于添加的结点是 red 结点，所以不会增加黑高度，所以性质 5 也不会被破坏。那 么能被破坏的就是性质 2 或者性质 4。假设该红黑树是一棵空树，则新插入的结点就会成 为根结点，由于新结点是红色的，所以破坏了性质 2 的要求根结点必须是黑色。如果该树 是一棵非空二叉树，则性质 2 不会被破坏，而破坏性质 4 的情况就是:新插入结点的父结 点也是红色结点。
 理清了可能违反的红黑树性质，那我们就来逐个情况的解决。在这里我们设置两个函 数 insert()函数和 keepRB()函数。insert()函数负责结点的插入，其过程按照一般的二叉查找 树的插入操作进行，但是在插入结点之后，我们调用 keepRB()函数来检查和恢复红黑树的 性质
 */
/**插入结点*/
template <typename DataType>
void RBT<DataType>::insert(RBTNode<DataType> *node) {
    //看不懂了
    
   
}
#endif /* RBT_hpp */
